""""
题目：用递归实现欧几里得算法  求两个正整数的最大公约数（GCD (a,b) = GCD (b,a%b)，当 b=0 时，所求即为 a）
欧几里得算法（又称辗转相除法）是求两个正整数最大公约数（GCD）的经典算法，核心原理是利用公式：GCD(a, b) = GCD(b, a % b)，直到其中一个数(a或者b)为 0，此时另一个非0的数即为所求的最大公约数。

示例验证（以 a=48，b=18 为例）：
第一步：GCD(48, 18) = GCD(18, 48%18) = GCD(18, 12)
第二步：GCD(18, 12) = GCD(12, 18%12) = GCD(12, 6)
第三步：GCD(12, 6) = GCD(6, 12%6) = GCD(6, 0)
终止：当 b=0 时，返回 a=6，即 48 和 18 的最大公约数是 6。

"""

def gcd(a, b):
    # 基线条件：b=0时，最大公约数为a
    if b == 0:
        return a
    # 递归条件：GCD(a,b) = GCD(b, a%b)
    #在欧几里得算法中，a 不需要大于等于 b，算法本身会自动处理 a < b 的情况，因为第一次取余操作会完成 “大小交换”。
   #当 a < b 时，a % b 的结果就是 a 此时算法会自动将 (a, b) 转换为 (b, a)，相当于完成了一次 “大小交换”。
    #欧几里得算法对 a 和 b 的大小没有要求，无论 a ≥ b 还是 a < b，算法都能通过取余操作自动调整顺序，正确计算最大公约数。因此，代码无需提前判断 a 和 b 的大小，直接使用即可。
    return gcd(b, a % b)

# 测试
if __name__ == "__main__":
    print(gcd(8, 12))   # 输出: 4（8和12的最大公约数）
    print(gcd(17, 5))   # 输出: 1（17和5互质）
    print(gcd(0, 5))    # 输出: 5（特殊情况处理） 当 b=0 时，GCD 为 a
    print(gcd(5, 0))  # 输出: 5（特殊情况处理） 当 b=0 时，GCD 为 a